A common problem in many systems is scheduling resources for servicing or some other operation. Generally, scheduling is based on some priority scheme where the resources have been assigned a priority based on criteria relevant to the operation of the particular system.
In routers, often a large pool of resources needs to be scheduled for some operation. For example, in traffic managers the pool consists of many traffic classes each having a time stamp. These traffic classes are scheduled for service (sending a packet) by sorting their time stamps, e.g., the traffic class with the smallest time stamp is scheduled for service.
Another example is aging of a flow in a flow table. Each flow has a last access time label and the flow that was least recently accessed is scheduled to be removed from the table.
Yet another example is a cache replacement algorithm. A cacheable resource is given a usage frequency count where the most frequently used resource is scheduled to be loaded into cache while the least frequently used resource in the cache is scheduled to be replaced.
These are all problems that can be abstracted as such: a dynamic, numeric key is given to each resource to indicate eligibility or priority, and operations are scheduled based on searching for the most eligible key. Usually this can be done with a heap data structure if the size of the pool remains constant. When the size of the pool changes dynamically and dramatically, a classical heap will require serial tree walks to maintain O(log N) maximum depth, limiting its performance.
The challenges in the field of resource scheduling continue to increase with demands for more and better techniques having greater performance and storage efficiency. Therefore, a need has arisen for a new system and method for providing a resource scheduler with guaranteed high performance and low storage requirements.